package com.my.study.structures.sort;

/**
 * @author Carlos
 * @version 1.0.0
 * @date 2023/2/23 21:40
 */
public class MyMergeSort {

    public static void main(String[] args) {
        int[] a = {1, 23, 2, 4, 2, 9};
        sort(a, 0, a.length - 1);
        System.out.println(a);
    }


    private static void sort(int[] a, int start, int end) {
        if (null == a || start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        sort(a, start, mid);
        sort(a, mid + 1, end);
        merge(a, start, mid, end);
    }

    private static void merge(int[] a, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];
        int index = 0;
        int f = start;
        int s = mid + 1;

        while (f <= mid && s <= end) {
            if (a[f] < a[s]) {
                tmp[index++] = a[f++];
            } else {
                tmp[index++] = a[s++];
            }
        }

        while (f <= mid) {
            tmp[index++] = a[f++];
        }

        while (s <= end) {
            tmp[index++] = a[s++];
        }


        for (int i = 0; i < index; i++) {
            a[start + i] = tmp[i];
        }

        tmp = null;
    }
}
